package com.alex.space.commons;

import org.apache.commons.lang3.time.StopWatch;

/**
 * @author Alex
 *         Created by Alex on 2017/12/28.
 */
public class HeapUtils {

    private static final int ARRAY_SIZE = 10;
    private static StopWatch stopWatch = new StopWatch();

    public static void main(String[] args) {
        int[] num = SearchUtils.generateDistinctRandomArray(ARRAY_SIZE);
//        int[] num = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
        System.out.println("Init array:");
        SearchUtils.printArray(num);

        stopWatch.start();

//        adjust_max_heap_recursive(num, num.length, 2);
//        adjust_max_heap(num, num.length, 2);
        build_max_heap(num, num.length);

        stopWatch.stop();

        System.out.println("time is " + stopWatch.getTime());

        SearchUtils.printArray(num);

    }

    /**
     * 构建最大堆
     */
    public static void build_max_heap(int[] datas, int length) {
        int i;
        //build max heap from the last parent node
        for (i = length / 2; i > 0; i--) {
            adjust_max_heap_recursive(datas, length, i);
        }
    }

    /**
     * 递归MAX-HEAPIFY
     */
    public static void adjust_max_heap_recursive(int[] num, int length, int i) {
        if (i < 1 || i > length) {
            System.out.println("error param i");
            return;
        }
        int left, right, largest;
        int temp;
        left = LEFT(i);   //left child
        right = RIGHT(i); //right child
        //find the largest value among left and rihgt and i.
        if (left <= length && num[left - 1] > num[i - 1]) {
            largest = left;
        } else {
            largest = i;
        }
        if (right <= length && num[right - 1] > num[largest - 1]) {
            largest = right;
        }
        //exchange i and largest
        if (largest != i) {
            temp = num[i - 1];
            num[i - 1] = num[largest - 1];
            num[largest - 1] = temp;
            //recursive call the function,adjust from largest
            adjust_max_heap_recursive(num, length, largest);
        }
    }

    /**
     * 循环MAX-HEAPIFY
     */
    public static void adjust_max_heap(int[] num, int length, int i) {
        int left, right, largest;
        int temp;
        while (true) {
            left = LEFT(i);   //left child
            right = RIGHT(i); //right child
            //find the largest value among left and rihgt and i.
            if (left <= length && num[left - 1] > num[i - 1]) {
                largest = left;
            } else {
                largest = i;
            }
            if (right <= length && num[right - 1] > num[largest - 1]) {
                largest = right;
            }
            //exchange i and largest
            if (largest != i) {
                temp = num[i - 1];
                num[i - 1] = num[largest - 1];
                num[largest - 1] = temp;
                i = largest;
                continue;
            } else {
                break;
            }
        }
    }

    private static int LEFT(int i) {
        return 2 * i;
    }

    private static int RIGHT(int i) {
        return 2 * i + 1;
    }

    private static int PARENT(int i) {
        return i / 2;
    }


}
